class Solution {
    public:
        int find_num(vector<int>& nums, int left, int right, int k) {
                    int mid = (left + right) / 2;
                            while (left <= right) {
                                            mid = (left + right) / 2;
                                                        if (nums[mid] > k) {
                                                                            right = mid - 1;
                                                        } else {
                                                                            left = mid + 1;
                                                        }
                            }
                                    return left;
        }
            vector<vector<int>> permute(vector<int>& nums) {
                        sort(nums.begin(), nums.end());
                                vector<vector<int>> arr;
                                        vector<int> new_nums;
                                                for (auto& num : nums) {
                                                                new_nums.push_back(num);
                                                }
                                                        arr.push_back(new_nums);
                                                                for (int i = nums.size() - 1; i > 0; i--) {
                                                                                if (nums[i - 1] < nums[i]) {
                                                                                                    sort(nums.begin() + i, nums.end());
                                                                                                                    // 二分查找，找到大于nums[i-1]的最小值
                                                                                                                                    int numsi_max = find_num(nums, i, nums.size() - 1, nums[i - 1]);
                                                                                                                                                    swap(nums[i - 1], nums[numsi_max]);
                                                                                                                                                                    i = nums.size();
                                                                                                                                                                                    vector<int> new_nums1;
                                                                                                                                                                                                    for (auto& num : nums) {
                                                                                                                                                                                                                            new_nums1.push_back(num);
                                                                                                                                                                                                    }
                                                                                                                                                                                                                    arr.push_back(new_nums1);
                                                                                }
                                                                }
                                                                        return arr;
            }
};
                                                                                                                                                                                                    }
                                                                                }
                                                                }
                                                }
            }
                                                        }
                                                        }
                            }
        }
}